home *** CD-ROM | disk | FTP | other *** search
/ Languguage OS 2 / Languguage OS II Version 10-94 (Knowledge Media)(1994).ISO / gnu / libg_261.zip / libg_261 / libg++ / src / BitSet.cc < prev    next >
C/C++ Source or Header  |  1994-05-11  |  20KB  |  1,007 lines
  1. /* 
  2. Copyright (C) 1988 Free Software Foundation
  3.     written by Doug Lea (dl@rocky.oswego.edu)
  4.  
  5. This file is part of the GNU C++ Library.  This library is free
  6. software; you can redistribute it and/or modify it under the terms of
  7. the GNU Library General Public License as published by the Free
  8. Software Foundation; either version 2 of the License, or (at your
  9. option) any later version.  This library is distributed in the hope
  10. that it will be useful, but WITHOUT ANY WARRANTY; without even the
  11. implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  12. PURPOSE.  See the GNU Library General Public License for more details.
  13. You should have received a copy of the GNU Library General Public
  14. License along with this library; if not, write to the Free Software
  15. Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
  16. */
  17.  
  18. /* 
  19.   BitSet class implementation
  20.  */
  21.  
  22. #ifdef __GNUG__
  23. #pragma implementation
  24. #endif
  25. #include <BitSet.h>
  26. #include <std.h>
  27. #include <limits.h>
  28. #include <Obstack.h>
  29. #include <AllocRing.h>
  30. #include <new.h>
  31. #include <builtin.h>
  32. #include <string.h>
  33. #include <strstream.h>
  34.  
  35. void BitSet::error(const char* msg) const
  36. {
  37.   (*lib_error_handler)("BitSet", msg);
  38. }
  39.  
  40. //  globals & constants
  41.  
  42. BitSetRep  _nilBitSetRep = { 0, 1, 0, {0} }; // nil BitSets point here
  43.  
  44. #define ONES               ((unsigned short)(~0L))
  45. #define MAXBitSetRep_SIZE  ((1 << (sizeof(short)*CHAR_BIT - 1)) - 1)
  46. #define MINBitSetRep_SIZE  16
  47.  
  48. #ifndef MALLOC_MIN_OVERHEAD
  49. #define MALLOC_MIN_OVERHEAD     4
  50. #endif
  51.  
  52. // break things up into .s indices and positions
  53.  
  54.  
  55. // mask out bits from left
  56.  
  57. static inline unsigned short lmask(int p)
  58. {
  59.   return ONES << p;
  60. }
  61.  
  62. // mask out high bits
  63.  
  64. static inline unsigned short rmask(int p)
  65. {
  66.   return ONES >> (BITSETBITS - 1 - p);
  67. }
  68.  
  69.  
  70. inline static BitSetRep* BSnew(int newlen)
  71. {
  72.   unsigned int siz = sizeof(BitSetRep) + newlen * sizeof(short) 
  73.     + MALLOC_MIN_OVERHEAD;
  74.   unsigned int allocsiz = MINBitSetRep_SIZE;;
  75.   while (allocsiz < siz) allocsiz <<= 1;
  76.   allocsiz -= MALLOC_MIN_OVERHEAD;
  77.   if (allocsiz >= MAXBitSetRep_SIZE * sizeof(short))
  78.     (*lib_error_handler)("BitSet", "Requested length out of range");
  79.     
  80.   BitSetRep* rep = (BitSetRep *) new char[allocsiz];
  81.   memset(rep, 0, allocsiz);
  82.   rep->sz = (allocsiz - sizeof(BitSetRep) + sizeof(short)) / sizeof(short);
  83.   return rep;
  84. }
  85.  
  86. BitSetRep* BitSetalloc(BitSetRep* old, const unsigned short* src, int srclen,
  87.                 int newvirt, int newlen)
  88. {
  89.   if (old == &_nilBitSetRep) old = 0;
  90.   BitSetRep* rep;
  91.   if (old == 0 || newlen >= old->sz)
  92.     rep = BSnew(newlen);
  93.   else
  94.     rep = old;
  95.  
  96.   rep->len = newlen;
  97.   rep->virt = newvirt;
  98.  
  99.   if (srclen != 0 && src != rep->s)
  100.     memcpy(rep->s, src, srclen * sizeof(short));
  101.   // BUG fix: extend virtual bit! 20 Oct 1992 Kevin Karplus
  102.   if (rep->virt)
  103.       memset(&rep->s[srclen], ONES, (newlen - srclen) * sizeof(short));
  104.   if (old != rep && old != 0) delete old;
  105.   return rep;
  106. }
  107.  
  108. BitSetRep* BitSetresize(BitSetRep* old, int newlen)
  109. {
  110.   BitSetRep* rep;
  111.   if (old == 0 || old == &_nilBitSetRep)
  112.   {
  113.     rep = BSnew(newlen);
  114.     rep->virt = 0;
  115.   }
  116.   else if (newlen >= old->sz)
  117.   {
  118.     rep = BSnew(newlen);
  119.     memcpy(rep->s, old->s, old->len * sizeof(short));
  120.     rep->virt = old->virt;
  121.     // BUG fix: extend virtual bit!  20 Oct 1992 Kevin Karplus
  122.     if (rep->virt)
  123.     memset(&rep->s[old->len], ONES, (newlen - old->len) * sizeof(short));
  124.     delete old;
  125.   }
  126.   else
  127.     {
  128.       rep = old;
  129.       if (rep->len < newlen)
  130.     memset(&rep->s[rep->len],
  131.            rep->virt ? ONES : 0,
  132.            (newlen - rep->len) * sizeof(short));
  133.     }
  134.  
  135.   rep->len = newlen;
  136.  
  137.   return rep;
  138. }
  139.  
  140. // same, for straight copy
  141.  
  142. BitSetRep* BitSetcopy(BitSetRep* old, const BitSetRep* src)
  143. {
  144.   BitSetRep* rep;
  145.   if (old == &_nilBitSetRep) old = 0;
  146.   if (src == 0 || src == &_nilBitSetRep)
  147.   {
  148.     if (old == 0)
  149.       rep = BSnew(0);
  150.     else
  151.       rep = old;
  152.     rep->len = 0;
  153.     rep->virt = 0;
  154.   }
  155.   else if (old == src) 
  156.     return old; 
  157.   else 
  158.   {
  159.     int newlen = src->len;
  160.     if (old == 0 || newlen > old->sz)
  161.     {
  162.       rep = BSnew(newlen);
  163.       if (old != 0) delete old;
  164.     }
  165.     else
  166.       rep = old;
  167.  
  168.     memcpy(rep->s, src->s, newlen * sizeof(short));
  169.     rep->len = newlen;
  170.     rep->virt = src->virt;
  171.   }
  172.   return rep;
  173. }
  174.  
  175.  
  176. // remove unneeded top bits
  177.  
  178. inline static void trim(BitSetRep* rep)
  179. {
  180.   int l = rep->len;
  181.   unsigned short* s = &(rep->s[l - 1]);
  182.  
  183.   if (rep->virt == 0)
  184.     while (l > 0 && *s-- == 0) --l;
  185.   else
  186.     while (l > 0 && *s-- == ONES) --l;
  187.   rep->len = l;
  188. }
  189.  
  190. int operator == (const BitSet& x, const BitSet& y)
  191. {
  192.   if (x.rep->virt != y.rep->virt)
  193.     return 0;
  194.   int xl = x.rep->len;
  195.   int yl = y.rep->len;
  196.  
  197.   unsigned short* xs = x.rep->s;
  198.   unsigned short* ys = y.rep->s;
  199.   if (xl<=yl)
  200.     {
  201.       if (memcmp((void*)xs, (void*)ys, xl * sizeof(short)))
  202.       return 0;
  203.       for (register int i=xl; i<yl; i++)
  204.         if (ys[i])
  205.       return 0;
  206.       return 1;
  207.     }
  208.   else
  209.     {
  210.       if (memcmp((void*)xs, (void*)ys, yl * sizeof(short)))
  211.       return 0;
  212.       for (register int i=yl; i<xl; i++)
  213.         if (xs[i]) 
  214.       return 0;
  215.       return 1;
  216.     }
  217. }
  218.  
  219. int operator <= (const BitSet& x, const BitSet& y)
  220. {
  221.   if (x.rep->virt > y.rep->virt)
  222.     return 0;
  223.  
  224.   int xl = x.rep->len;
  225.   int yl = y.rep->len; 
  226.  
  227.   unsigned short* xs = x.rep->s;
  228.   unsigned short* ys = y.rep->s;
  229.   unsigned short* topx = &(xs[xl]);
  230.   unsigned short* topy = &(ys[yl]);
  231.  
  232.   while (xs < topx && ys < topy)
  233.   {
  234.     unsigned short a = *xs++;
  235.     unsigned short b = *ys++;
  236.     if ((a | b) != b)
  237.       return 0;
  238.   }
  239.   if (xl == yl)
  240.     return x.rep->virt <= y.rep->virt;
  241.   else if (xl < yl)
  242.     return !x.rep->virt;
  243.   else
  244.     return y.rep->virt;
  245. }
  246.  
  247.  
  248. int operator < (const BitSet& x, const BitSet& y)
  249. {
  250.   if (x.rep->virt > y.rep->virt)
  251.     return 0;
  252.  
  253.   int xl = x.rep->len;
  254.   int yl = y.rep->len;
  255.  
  256.   unsigned short* xs = x.rep->s;
  257.   unsigned short* ys = y.rep->s;
  258.   unsigned short* topx = &(xs[xl]);
  259.   unsigned short* topy = &(ys[yl]);
  260.   int one_diff = 0;
  261.   while (xs < topx && ys < topy)
  262.   {
  263.     unsigned short a = *xs++;
  264.     unsigned short b = *ys++;
  265.     unsigned short c = a | b;
  266.     if (c != b)
  267.       return 0;
  268.     else if (c != a)
  269.       one_diff = 1;
  270.   }
  271.   if (xl == yl)
  272.     return x.rep->virt < y.rep->virt || 
  273.       (one_diff && x.rep->virt == y.rep->virt);
  274.   else if (xl < yl)
  275.     return !x.rep->virt;
  276.   else
  277.     return y.rep->virt;
  278. }
  279.  
  280.  
  281.  
  282. int BitSet::empty() const
  283. {
  284.   if (rep->virt == 1)
  285.     return 0;
  286.  
  287.   unsigned short* bots = rep->s;
  288.   unsigned short* s = &(bots[rep->len - 1]);
  289.   while (s >= bots) if (*s-- != 0) return 0;
  290.   return 1;
  291. }
  292.  
  293.  
  294. int BitSet::count(int b) const
  295. {
  296.   if (b == rep->virt)
  297.     return -1;
  298.   int l = 0;
  299.   unsigned short* s = rep->s;
  300.   unsigned short* tops = &(s[rep->len]);
  301.   if (b == 1)
  302.   {
  303.     while (s < tops)
  304.     {
  305.       unsigned short a = *s++;
  306.       for (int i = 0; i < BITSETBITS && a != 0; ++i)
  307.       {
  308.         if (a & 1)
  309.           ++l;
  310.         a >>= 1;
  311.       }
  312.     }
  313.   }
  314.   else
  315.   {
  316.     unsigned short maxbit = 1 << (BITSETBITS - 1);
  317.     while (s < tops)
  318.     {
  319.       unsigned short a = *s++;
  320.       for (int i = 0; i < BITSETBITS; ++i)
  321.       {
  322.         if ((a & maxbit) == 0)
  323.           ++l;
  324.         a <<= 1;
  325.       }
  326.     }
  327.   }
  328.   return l;
  329. }
  330.  
  331. BitSetRep* BitSetcmpl(const BitSetRep* src, BitSetRep* r)
  332. {
  333.   r = BitSetcopy(r, src);
  334.   r->virt = !src->virt;
  335.   unsigned short* rs = r->s;
  336.   unsigned short* topr = &(rs[r->len]);
  337.   if (r->len == 0)
  338.     *rs = ONES;
  339.   else
  340.   {
  341.     while (rs < topr)
  342.     {
  343.       unsigned short cmp = ~(*rs);
  344.       *rs++ = cmp;
  345.     }
  346.   }
  347.   trim(r);
  348.   return r;
  349. }
  350.  
  351.  
  352. BitSetRep* BitSetop(const BitSetRep* x, const BitSetRep* y, 
  353.                     BitSetRep* r, char op)
  354. {
  355.   int xrsame = x == r;
  356.   int yrsame = y == r;
  357.   int xv = x->virt;
  358.   int yv = y->virt;
  359.   int xl = x->len;
  360.   int yl = y->len;
  361.   int rl = (xl >= yl)? xl : yl;
  362.  
  363.   r = BitSetresize(r, rl);
  364.   unsigned short* rs = r->s;
  365.   unsigned short* topr = &(rs[rl]);
  366.  
  367.   int av, bv;
  368.   const unsigned short* as;
  369.   const unsigned short* topa;
  370.   const unsigned short* bs;
  371.   const unsigned short* topb;
  372.   
  373.   if (xl <= yl)
  374.   {
  375.     as = (xrsame)? r->s : x->s;
  376.     av = xv;
  377.     topa = &(as[xl]);
  378.     bs = (yrsame)? r->s : y->s;
  379.     bv = yv;
  380.     topb = &(bs[yl]);
  381.   }
  382.   else
  383.   {
  384.     as = (yrsame)? r->s : y->s;
  385.     av = yv;
  386.     topa = &(as[yl]);
  387.     bs = (xrsame)? r->s : x->s;
  388.     bv = xv;
  389.     topb = &(bs[xl]);
  390.     if (op == '-')              // reverse sense of difference
  391.       op = 'D';
  392.   }
  393.  
  394.   switch (op)
  395.   {
  396.   case '&':
  397.     r->virt = av & bv;
  398.     while (as < topa) *rs++ = *as++ & *bs++;
  399.     if (av)
  400.       while (rs < topr) *rs++ = *bs++;
  401.     else
  402.       while (rs < topr) *rs++ = 0;
  403.     break;
  404.   case '|':
  405.     r->virt = av | bv;
  406.     while (as < topa) *rs++ = *as++ | *bs++;
  407.     if (av)
  408.       while (rs < topr) *rs++ = ONES;
  409.     else
  410.       while (rs < topr) *rs++ = *bs++;
  411.     break;
  412.   case '^':
  413.     r->virt = av ^ bv;
  414.     while (as < topa) *rs++ = *as++ ^ *bs++;
  415.     if (av)
  416.       while (rs < topr) *rs++ = ~(*bs++);
  417.     else
  418.       while (rs < topr) *rs++ = *bs++;
  419.     break;
  420.   case '-':
  421.     r->virt = av & ~(bv);
  422.     while (as < topa) *rs++ = *as++ & ~(*bs++);
  423.     if (av)
  424.       while (rs < topr) *rs++ = ~(*bs++);
  425.     else
  426.       while (rs < topr) *rs++ = 0;
  427.     break;
  428.   case 'D':
  429.     r->virt = ~(av) & (bv);
  430.     while (as < topa) *rs++ = ~(*as++) & (*bs++);
  431.     if (av)
  432.       while (rs < topr) *rs++ = 0;
  433.     else
  434.       while (rs < topr) *rs++ = *bs++;
  435.     break;
  436.   }
  437.   trim(r);
  438.   return r;
  439. }
  440.  
  441.  
  442. void BitSet::set(int p)
  443. {
  444.   if (p < 0) error("Illegal bit index");
  445.  
  446.   int index = BitSet_index(p);
  447.   int pos   = BitSet_pos(p);
  448.  
  449.   if (index >= rep->len)
  450.   {
  451.     if (rep->virt)
  452.       return;
  453.     else
  454.       rep = BitSetresize(rep, index+1);
  455.   }
  456.  
  457.   rep->s[index] |= (1 << pos);
  458. }
  459.  
  460. void BitSet::clear()
  461. {
  462.   if (rep->len > 0) memset(rep->s, 0, rep->sz * sizeof(short));
  463.   rep->len = rep->virt = 0;
  464. }
  465.  
  466. void BitSet::clear(int p)
  467. {
  468.   if (p < 0) error("Illegal bit index");
  469.   int index = BitSet_index(p);
  470.   if (index >= rep->len)
  471.   {
  472.     if (rep->virt == 0)
  473.       return;
  474.     else
  475.       rep = BitSetresize(rep, index+1);
  476.   }
  477.   rep->s[index] &= ~(1 << BitSet_pos(p));
  478. }
  479.  
  480. void BitSet::invert(int p)
  481. {
  482.   if (p < 0) error("Illegal bit index");
  483.   int index = BitSet_index(p);
  484.   if (index >= rep->len) rep = BitSetresize(rep, index+1);
  485.   rep->s[index] ^= (1 << BitSet_pos(p));
  486. }
  487.  
  488. void BitSet::set(int from, int to)
  489. {
  490.   if (from < 0 || from > to) error("Illegal bit index");
  491.  
  492.   int index1 = BitSet_index(from);
  493.   int pos1   = BitSet_pos(from);
  494.   
  495.   if (rep->virt && index1 >= rep->len)
  496.     return;
  497.  
  498.   int index2 = BitSet_index(to);
  499.   int pos2   = BitSet_pos(to);
  500.  
  501.   if (index2 >= rep->len)
  502.     rep = BitSetresize(rep, index2+1);
  503.  
  504.   unsigned short* s = &(rep->s[index1]);
  505.   unsigned short m1 = lmask(pos1);
  506.   unsigned short m2 = rmask(pos2);
  507.   if (index2 == index1)
  508.     *s |= m1 & m2;
  509.   else
  510.   {
  511.     *s++ |= m1;
  512.     unsigned short* top = &(rep->s[index2]);
  513.     *top |= m2;
  514.     while (s < top)
  515.       *s++ = ONES;
  516.   }
  517. }
  518.  
  519. void BitSet::clear(int from, int to)
  520. {
  521.   if (from < 0 || from > to) error("Illegal bit index");
  522.  
  523.   int index1 = BitSet_index(from);
  524.   int pos1   = BitSet_pos(from);
  525.   
  526.   if (!rep->virt && index1 >= rep->len)
  527.     return;
  528.  
  529.   int index2 = BitSet_index(to);
  530.   int pos2   = BitSet_pos(to);
  531.  
  532.   if (index2 >= rep->len)
  533.     rep = BitSetresize(rep, index2+1);
  534.  
  535.   unsigned short* s = &(rep->s[index1]);
  536.   unsigned short m1 = lmask(pos1);
  537.   unsigned short m2 = rmask(pos2);
  538.   if (index2 == index1)
  539.     *s &= ~(m1 & m2);
  540.   else
  541.   {
  542.     *s++ &= ~m1;
  543.     unsigned short* top = &(rep->s[index2]);
  544.     *top &= ~m2;
  545.     while (s < top)
  546.       *s++ = 0;
  547.   }
  548. }
  549.  
  550. void BitSet::invert(int from, int to)
  551. {
  552.   if (from < 0 || from > to) error("Illegal bit index");
  553.  
  554.   int index1 = BitSet_index(from);
  555.   int pos1   = BitSet_pos(from);
  556.   int index2 = BitSet_index(to);
  557.   int pos2   = BitSet_pos(to);
  558.  
  559.   if (index2 >= rep->len)
  560.     rep = BitSetresize(rep, index2+1);
  561.  
  562.   unsigned short* s = &(rep->s[index1]);
  563.   unsigned short m1 = lmask(pos1);
  564.   unsigned short m2 = rmask(pos2);
  565.   if (index2 == index1)
  566.     *s ^= m1 & m2;
  567.   else
  568.   {
  569.     *s++ ^= m1;
  570.     unsigned short* top = &(rep->s[index2]);
  571.     *top ^= m2;
  572.     while (s < top)
  573.     {
  574.       unsigned short cmp = ~(*s);
  575.       *s++ = cmp;
  576.     }
  577.   }
  578. }
  579.  
  580.  
  581. int BitSet::test(int from, int to) const
  582. {
  583.   if (from < 0 || from > to) return 0;
  584.  
  585.   int index1 = BitSet_index(from);
  586.   int pos1   = BitSet_pos(from);
  587.   
  588.   if (index1 >= rep->len)
  589.     return rep->virt;
  590.  
  591.   int index2 = BitSet_index(to);
  592.   int pos2   = BitSet_pos(to);
  593.  
  594.   if (index2 >= rep->len)
  595.   {
  596.     if (rep->virt)
  597.       return 1;
  598.     else 
  599.     {
  600.       index2 = rep->len - 1;
  601.       pos2 = BITSETBITS - 1;
  602.     }
  603.   }
  604.  
  605.   unsigned short* s = &(rep->s[index1]);
  606.   unsigned short m1 = lmask(pos1);
  607.   unsigned short m2 = rmask(pos2);
  608.  
  609.   if (index2 == index1)
  610.     return (*s & m1 & m2) != 0;
  611.   else
  612.   {
  613.     if (*s++ & m1)
  614.       return 1;
  615.     unsigned short* top = &(rep->s[index2]);
  616.     if (*top & m2)
  617.       return 1;
  618.     while (s < top)
  619.       if (*s++ != 0) 
  620.         return 1;
  621.     return 0;
  622.   }
  623. }
  624.  
  625. int BitSet::next(int p, int b) const
  626. {
  627.   ++p;
  628.   int index = BitSet_index(p);
  629.   int pos   = BitSet_pos(p);
  630.  
  631.   int l = rep->len;
  632.   
  633.   if (index >= l)
  634.   {
  635.     if (rep->virt == b)
  636.       return p;
  637.     else
  638.       return -1;
  639.   }
  640.   int j = index;
  641.   unsigned short* s = rep->s;
  642.   unsigned short a = s[j] >> pos;
  643.   int i = pos;
  644.  
  645.   if (b == 1)
  646.   {
  647.     for (; i < BITSETBITS && a != 0; ++i)
  648.     {
  649.       if (a & 1)
  650.         return j * BITSETBITS + i;
  651.       a >>= 1;
  652.     }
  653.     for (++j; j < l; ++j)
  654.     {
  655.       a = s[j];
  656.       for (i = 0; i < BITSETBITS && a != 0; ++i)
  657.       {
  658.         if (a & 1)
  659.           return j * BITSETBITS + i;
  660.         a >>= 1;
  661.       }
  662.     }
  663.     if (rep->virt)
  664.       return j * BITSETBITS;
  665.     else
  666.       return -1;
  667.   }
  668.   else
  669.   {
  670.     for (; i < BITSETBITS; ++i)
  671.     {
  672.       if ((a & 1) == 0)
  673.         return j * BITSETBITS + i;
  674.       a >>= 1;
  675.     }
  676.     for (++j; j < l; ++j)
  677.     {
  678.       a = s[j];
  679.       if (a != ONES)
  680.       {
  681.         for (i = 0; i < BITSETBITS; ++i)
  682.         {
  683.           if ((a & 1) == 0)
  684.             return j * BITSETBITS + i;
  685.           a >>= 1;
  686.         }
  687.       }
  688.     }
  689.     if (!rep->virt)
  690.       return j * BITSETBITS;
  691.     else
  692.       return -1;
  693.   }
  694. }
  695.  
  696. int BitSet::prev(int p, int b) const
  697. {
  698.   if (--p < 0)
  699.     return -1;
  700.  
  701.   int index = BitSet_index(p);
  702.   int pos   = BitSet_pos(p);
  703.  
  704.   unsigned short* s = rep->s;
  705.   int l = rep->len;
  706.  
  707.   if (index >= l)
  708.   {
  709.     if (rep->virt == b)
  710.       return p;
  711.     else
  712.     {
  713.       index = l - 1;
  714.       pos = BITSETBITS - 1;
  715.     }
  716.   }
  717.  
  718.   int j = index;
  719.   unsigned short a = s[j];
  720.  
  721.   int i = pos;
  722.   unsigned short maxbit = 1 << pos;
  723.  
  724.   if (b == 1)
  725.   {
  726.     for (; i >= 0 && a != 0; --i)
  727.     {
  728.       if (a & maxbit)
  729.         return j * BITSETBITS + i;
  730.       a <<= 1;
  731.     }
  732.     maxbit = 1 << (BITSETBITS - 1);
  733.     for (--j; j >= 0; --j)
  734.     {
  735.       a = s[j];
  736.       for (i = BITSETBITS - 1; i >= 0 && a != 0; --i)
  737.       {
  738.         if (a & maxbit)
  739.           return j * BITSETBITS + i;
  740.         a <<= 1;
  741.       }
  742.     }
  743.     return -1;
  744.   }
  745.   else
  746.   {
  747.     if (a != ONES)
  748.     {
  749.       for (; i >= 0; --i)
  750.       {
  751.         if ((a & maxbit) == 0)
  752.           return j * BITSETBITS + i;
  753.         a <<= 1;
  754.       }
  755.     }
  756.     maxbit = 1 << (BITSETBITS - 1);
  757.     for (--j; j >= 0; --j)
  758.     {
  759.       a = s[j];
  760.       if (a != ONES)
  761.       {
  762.         for (i = BITSETBITS - 1; i >= 0; --i)
  763.         {
  764.           if ((a & maxbit) == 0)
  765.             return j * BITSETBITS + i;
  766.           a <<= 1;
  767.         }
  768.       }
  769.     }
  770.     return -1;
  771.   }
  772. }
  773.  
  774. int BitSet::last(int b) const
  775. {
  776.   if (b == rep->virt)
  777.     return -1;
  778.   else
  779.     return prev((rep->len) * BITSETBITS, b);
  780. }
  781.  
  782.  
  783. extern AllocRing _libgxx_fmtq;
  784.  
  785. const char* BitSettoa(const BitSet& x, char f, char t, char star)
  786. {
  787.   trim(x.rep);
  788.   int wrksiz = (x.rep->len + 1) * BITSETBITS + 2;
  789.   char* fmtbase = (char *) _libgxx_fmtq.alloc(wrksiz);
  790.   ostrstream stream(fmtbase, wrksiz);
  791.   
  792.   x.printon(stream, f, t, star);
  793.   stream << ends;
  794.   return fmtbase;
  795. }
  796.  
  797. #if defined(__GNUG__) && !defined(_G_NO_NRV)
  798.  
  799. BitSet shorttoBitSet(unsigned short w) return r
  800. {
  801.   r.rep = BitSetalloc(0, &w, 1, 0, 2);  trim(r.rep);
  802. }
  803.  
  804. BitSet longtoBitSet(unsigned long w) return r;
  805. {
  806.   unsigned short u[2];
  807.   u[0] = w & ((unsigned short)(~(0)));
  808.   u[1] = w >> BITSETBITS;
  809.   r.rep = BitSetalloc(0, &u[0], 2, 0, 3);
  810.   trim(r.rep);
  811. }
  812.  
  813. BitSet atoBitSet(const char* s, char f, char t, char star) return r
  814. {
  815.   int sl = strlen(s);
  816.   if (sl != 0)
  817.   {
  818.     r.rep = BitSetresize(r.rep, sl / BITSETBITS + 1);
  819.     unsigned short* rs = r.rep->s;
  820.     unsigned short a = 0;
  821.     unsigned short m = 1;
  822.     char lastch = 0;
  823.     unsigned int i = 0;
  824.     unsigned int l = 1;
  825.     for(;;)
  826.     {
  827.       char ch = s[i];
  828.       if (ch == t)
  829.         a |= m;
  830.       else if (ch == star)
  831.       {
  832.         if (r.rep->virt = lastch == t)
  833.           *rs = a | ~(m - 1);
  834.         else
  835.           *rs = a;
  836.         break;
  837.       }
  838.       else if (ch != f)
  839.       {
  840.         *rs = a;
  841.         break;
  842.       }
  843.       lastch = ch;
  844.       if (++i == sl)
  845.       {
  846.         *rs = a;
  847.         break;
  848.       }
  849.       else if (i % BITSETBITS == 0)
  850.       {
  851.         *rs++ = a;
  852.         a = 0;
  853.         m = 1;
  854.         ++l;
  855.       }
  856.       else
  857.         m <<= 1;
  858.     }
  859.     r.rep->len = l;
  860.     trim(r.rep);
  861.   }
  862.   return;
  863. }
  864.  
  865. #else
  866.  
  867. BitSet shorttoBitSet(unsigned short w) 
  868. {
  869.   BitSet r;
  870.   r.rep = BitSetalloc(0, &w, 1, 0, 2);  trim(r.rep);
  871.   return r;
  872. }
  873.  
  874. BitSet longtoBitSet(unsigned long w)
  875. {
  876.   BitSet r;
  877.   unsigned short u[2];
  878.   u[0] = w & ((unsigned short)(~(0)));
  879.   u[1] = w >> BITSETBITS;
  880.   r.rep = BitSetalloc(0, &u[0], 2, 0, 3);
  881.   trim(r.rep);
  882.   return r;
  883. }
  884.  
  885. BitSet atoBitSet(const char* s, char f, char t, char star) 
  886. {
  887.   BitSet r;
  888.   int sl = strlen(s);
  889.   if (sl != 0)
  890.   {
  891.     r.rep = BitSetresize(r.rep, sl / BITSETBITS + 1);
  892.     unsigned short* rs = r.rep->s;
  893.     unsigned short a = 0;
  894.     unsigned short m = 1;
  895.     char lastch = 0;
  896.     unsigned int i = 0;
  897.     unsigned int l = 1;
  898.     for(;;)
  899.     {
  900.       char ch = s[i];
  901.       if (ch == t)
  902.         a |= m;
  903.       else if (ch == star)
  904.       {
  905.         if (r.rep->virt = lastch == t)
  906.           *rs = a | ~(m - 1);
  907.         else
  908.           *rs = a;
  909.         break;
  910.       }
  911.       else if (ch != f)
  912.       {
  913.         *rs = a;
  914.         break;
  915.       }
  916.       lastch = ch;
  917.       if (++i == sl)
  918.       {
  919.         *rs = a;
  920.         break;
  921.       }
  922.       else if (i % BITSETBITS == 0)
  923.       {
  924.         *rs++ = a;
  925.         a = 0;
  926.         m = 1;
  927.         ++l;
  928.       }
  929.       else
  930.         m <<= 1;
  931.     }
  932.     r.rep->len = l;
  933.     trim(r.rep);
  934.   }
  935.   return r;
  936. }
  937.  
  938. #endif
  939.  
  940. ostream& operator << (ostream& s, const BitSet& x)
  941. {
  942.   if (s.opfx())
  943.     x.printon(s);
  944.   return s;
  945. }
  946.  
  947. void BitSet::printon(ostream& os, char f, char t, char star) const
  948. // FIXME:  Does not respect s.width()!
  949. {
  950.   trim(rep);
  951.   register streambuf* sb = os.rdbuf();
  952.   const unsigned short* s = rep->s;
  953.   const unsigned short* top = &(s[rep->len - 1]);
  954.  
  955.   while (s < top)
  956.   {
  957.     unsigned short a = *s++;
  958.     for (int j = 0; j < BITSETBITS; ++j)
  959.     {
  960.       sb->sputc((a & 1)? t : f);
  961.       a >>= 1;
  962.     }
  963.   }
  964.  
  965.   if (!rep->virt)
  966.   {
  967.     unsigned short a = *s;
  968.     if (rep->len != 0)
  969.     {
  970.       for (int j = 0; j < BITSETBITS && a != 0; ++j)
  971.       {
  972.         sb->sputc((a & 1)? t : f);
  973.         a >>= 1;
  974.       }
  975.     }
  976.     sb->sputc(f);
  977.   }
  978.   else
  979.   {
  980.     unsigned short a = *s;
  981.     unsigned short mask = ONES;
  982.     unsigned short himask = (1 << (BITSETBITS - 1)) - 1;
  983.     if (rep->len != 0)
  984.     {
  985.       for (int j = 0; j < BITSETBITS && a != mask; ++j)
  986.       {
  987.         sb->sputc((a & 1)? t : f);
  988.         a = (a >> 1) & himask;
  989.         mask = (mask >> 1) & himask;
  990.       }
  991.     }
  992.     sb->sputc(t);
  993.   }
  994.  
  995.   sb->sputc(star);
  996. }
  997.  
  998. int BitSet::OK() const
  999. {
  1000.   int v = rep != 0;             // have a rep
  1001.   v &= rep->len <= rep->sz;     // within bounds
  1002.   v &= rep->virt == 0 || rep->virt == 1; // valid virtual bit
  1003.   if (!v) error("invariant failure");
  1004.   return v;
  1005. }
  1006.  
  1007.